Matching patches between two images, or between regions of the images, is also referred to as computing a nearest neighbor field and is a common technique used for image processing and computer graphics applications. Patches of an image may be compared as each pixel of the image, or may be a larger region of the image that includes a grid of multiple pixels. One technique for determining matching patches between two images is to exhaustively search for the best matching patch in one of the images for every patch in the other image. Although this technique is a simple algorithm, it is computationally expensive and time-consuming.
There are other more efficient algorithms that can be utilized to speed up the matching process, such as by utilizing a spatial constraint that adjacent patches in one image tend to have the same spatial relationship with the matching patches in the other image. However, these algorithms are directed to reconstructing one image from the other and often produce patch matches that are spatially incoherent, with the resulting nearest neighbor fields being based on reconstruction errors. Conventional techniques and algorithms to compute nearest neighbor fields between images do not enforce spatial coherency of the matching patches, and may not match a patch in one image to the respective, same patch in another image. For example, a white color patch in one image may be matched to any number of white color patches in another image without maintaining the spatial coherency of the actual corresponding patches in the two images.
Optical flow is the problem of inferring the apparent motion between images, and conventional algorithms for optical flow are utilized to compute a motion field, such as for optical flow registration, which is useful for image tracking, motion segmentation, and other motion processing applications. A nearest neighbor field typically provides only a very noisy estimate of the true optical flow field for the images. A motion field can be computed between two images, where the direction and magnitude of optic flow at each location is represented by the direction and length of arrows in the motion field. A motion determination between images can be utilized to track object motion, such as in video frames. For example, in a robotics application, cameras may capture two or more separate images of a scene and/or subject from slightly different perspectives and combine the separate images into one image to reduce or eliminate noise in the images. The noise effect will be different in each of the images, and the combined image is a smoothed combination of the separate images that reduces or eliminates the noise effect of each image.
Although optical flow algorithms can enforce the spatial coherency of pixels and/or patches between images, the conventional algorithms assume that the pixel motion of objects (e.g., object displacement) from one image to the next is very small. Further, optic flow registration algorithms that extract feature points do not provide a dense motion field of the images. Additionally, the conventional algorithms often produce incorrect results because they are initialized to start from an initial motion field that is typically set to zero everywhere, and therefore cannot account for a large motion between two images.